エイシング プログラミング コンテスト 2020

https://gyazo.com/7de3589758d166915f760316cf5f6fb2

https://gyazo.com/7a65641796a5dde7c39dff799a4e7c76

二乗の項があるのでx,y,zは100未満、全探索しても10^6だから十分余裕がある

それをN回やらないといけないことが問題

一旦細かいこと考えずに素朴にN回やるコードを書いてテスト通ることを確認

10^10

code:python

if v == n:

ret += 1

elif v > n:

break

計算結果がnに一致する時、retを増やして、小さい時には何もしてない

一番外のnについてのループは最も大きく1周して、その過程でもっと小さいnの場合の答えも数えたらnについてのループ不要だな、といって書き換える

code:python

def solve(N):

from math import sqrt, floor

n = N

for x in range(1, floor(sqrt(n))):

v0 = x * x

for y in range(1, floor(sqrt(n))):

v1 = v0 + y * y + y * x

if v1 >= n:

break

for z in range(1, floor(sqrt(n))):

v = v1 + z * z + y * z + z * x

if v > n:

break

https://gyazo.com/428c4eee4eb087c1349756bdb8805ce7

おっ、コンテスト中提出のPyPyで最高速度のコードだ、何か実績解除とかないのかな？

https://gyazo.com/7a40546dbd35aecf59693a91c166bcd3

20万桁の二進数が渡される

つまりそれを数値として扱うことは無謀

問題の関数を素朴に実装して1ステップかけた値を観察してみたら、結構小さな値ばかり

素朴に実装=数値を二進法文字列にして1の個数をカウントする

code:python

def f(n):

p = bin(n).count("1")

return n % p

code::

popcountで剰余を取るのであっという間に小さくなるのだ

20万桁の二進数が渡されても、一回変換すれば最大20万になる。

16桁ぐらいなので、もう1ステップ計算したら上記のテーブルに到着する

つまり20万桁の二進数の1ステップ後の値を軽く求めればOK

この「軽く求める」に関して、問題条件を素朴に受けると20万桁の二進数の各桁ビット反転した20万個の値に対して剰余の計算が必要になって明らかにダメ

そこで20万個の値に対する剰余計算を、あらかじめ「2の累乗の剰余」を求めておくことで定数オーダーにする

まずはこの高速化をしないで素朴に書いてテストを通した

提出したらREになった

1つしかビットが立ってない入力の時に、そのビットが反転したら最初から0

それに気づかずに剰余を計算しようとするとpopcountもゼロなのでゼロ除算になる

素朴解法での剰余と高速解法での剰余が一致することをテストしてから置き換えた(半ばのコメントアウトしてるところ)

数値を二進法文字列にして1の個数をカウントするの遅そうに思うかもしれないけど全体では205msecで速い方から1ページに収まってました

実行時間の大きな割合を占めていないコードを高速化しても意味がないので手抜きしてます

code:python

def solve(N, X):

o1 = ord("1")

def f(n):

p = bin(n).count("1")

return n % p

for i in range(1, 20):

x = f(i)

if x == 0:

else:

numOne = X.count(o1)

v = 0

mod = numOne + 1

p = 1

for j in range(N):

v *= 2

v %= mod

v += 1

p *= 2

p %= mod

xmod_p1 = v % mod # X mod (bc(X) + 1)

xmod_m1 = 0 # X mod (bc(X) - 1)

if numOne > 1:

p = 1

v = 0

mod = numOne - 1

for j in range(N):

v *= 2

v %= mod

v += 1

xmod_m1 = v % mod

p *= 2

p %= mod

for i in range(N):

mod = numOne - 1

if mod == 0:

# already 0

continue

else:

mod = numOne + 1

# v = 0

# for j in range(N):

# v *= 2

# v %= mod

# v += 1

# v %= mod

# debug(": v, v2", v, v2)

# assert v == v2

v = v2

if v == 0:

continue

if v < 20:

continue

v = f(v)

return ret

解けなかった問題の感想

Dが終わった時点で残り35分、普段のペースから考えて解けない可能性が高いだろうなと諦め気味(自分に負けてる)

ラクダが何番目までにいたいかのKの値でソートして順番に「先頭グループに入れるか、入れないか」の二択で、先頭グループのサイズを定義域にしてDP…

このDP、二乗のオーダーだからTLEなのでは…

とりあえず素朴にDPしてみる(残り15分)

テストケース1は通るが、残りは落ちる

このバグを直したとしてもTLEの問題が…

なぜフェイルするのか眺めてて、残り6分くらいで「後ろが好きなラクダもいる」とようやく気付いた

Kの小さい順に判断していくと「一番後ろの時だけとても喜ぶラクダ」の判断タイミングが遅れて最適解にならない

諦めてFを見る(残り3分)

これの方が簡単では？？

→簡単ではなかった

本当に簡単かどうか解いてないからわからないが、残り35分の段階で両方の問題を見るべきだったかもな

よかったこと

何度か「素朴に」って書いてるように、まず素朴に書いてから高速化するアプローチを取った

これは良いと思う